Human beings generally have little problem in recognizing “perceptual similarity” between different shapes. For example, people can easily tell that chairs in different sizes and styles are all chairs, or that instances of a letter written in different fonts or handwriting are all the same letter. This type of qualitative recognition is considerably more difficult to carry out by computer. There has been a great deal of research done on algorithms that computers can use to recognize and classify different shapes, but no one has yet found a generic method for shape classification that can approach the speed and reliability of human perception.
A useful method for computerized shape comparison is described by Kupeev and Wolfson in an article entitled, “A New Method of Estimating Shape Similarity,” published in Pattern Recognition Letters 17:8 (1996), pages 873–887, which is incorporated herein by reference. The authors introduce the notion of a G-graph G(K), which represents a geometrical structure of a contour K and the locations and sizes of “lumps” formed by the contour relative to the axes of a Cartesian frame. Contours that are similar will have G-graph representations that are either isomorphic or can be reduced to isomorphism by a technique described in the article. The authors present a method for computing a similarity distance between the contours, based on “trimming the leaves” of the G-graphs to generate a sequence of isomorphic pairs of graphs. This procedure is repeated for multiple, different relative orientations of the contours being compared. The similarity of the contours is determined by the minimum of the distance of the graphs over all the orientations.
The G-graph method was found by the authors to give good results when applied to recognizing arbitrary, freehand letters and other shapes. The method is computationally efficient and gives good recognition results as compared with other methods known in the art for automated shape comparison. The major computational cost of the method has to do with manipulation of the G-graphs themselves for calculating isomorphism.